package Array;

/**
 * 238. 除自身以外数组的乘积
 * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
 * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
 * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
 *
 * 解题思路：
 * 这道题首先的思路就是，定义一个存储 数组下标和对应值的map，然后遍历数组，每次遍历keyset，计算除当前i位的其他元素乘积即可，但是此种思路，时间复杂度是
 * O（n*2）, 不满足要求，所以我们要换一种思路解决问题。
 * 正确思路：
 *    我们可以作分割， 在数组中当前i位置的元素， 可以分为两部分，i左边的元素乘积leftRes 和 i右边的元素乘积RightRes， 则当前i位的乘积就是 leftRes * rightRes
 * 所以数组中每个位置计算当前的leftRes[i] 与 rightRes[i]，实时更新leftRes和rightRes的值，先给answer[i]赋值leftRes，然后再去乘以rightRes就可以解决不用空间的问题。
   解题步骤：
     1： 定义返回数组answer，数组的大小是nums.length，并且初始化值为1， 乘积的初始化值默认取1，避免0的干扰。
     2： 定义leftRes和rightRes，leftRes初始值为1，用来记录当前位置i的左半边和右半边的乘积。
     3：
       3.1 遍历数组，计算leftRes，并将answer[i] 赋值， answer[i] = leftRes（i-1）；
       3.2 然后倒序遍历数组，计算rightRes的值，乘以answer[i]即可 , 用倒序遍历的原因是需要知道右半部分的乘积，所以起点从最右边计算
     4：返回结果answer
  总结：这道题体现了分治思想，分而治之，然后再将结果合并。
 */
public class ProductExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        if(nums.length == 0){
            return null;
        }
        int [] answer = new int[nums.length];
        if(nums.length == 1){
            answer[0] = nums[0];
            return answer;
        }
        // 初始化answer
        for (int i = 0; i < answer.length; i++) {
            answer[i] = 1;
        }
        // 定义leftRes 和 RightRes
        int leftRes = 1;
        int rightRes = 1;
        // 计算leftRes,更新answer
        for (int i = 0; i <nums.length ; i++) {
            // 当前位就是i-1的乘积，也就是leftRes
            answer[i] = leftRes;
            // 更新leftRes
            leftRes *= nums[i];
        }
        // 计算rightRes,更新answer
        for (int i = nums.length-1; i >= 0 ; i--) {
            answer[i] *= rightRes;
            rightRes *= nums[i];
        }
        return answer;
    }
}
